//给你两个整数 n 和 k 。 
//
// 对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。 
//
// 返回长度为 n 的 k-avoiding 数组的可能的最小总和。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 5, k = 4
//输出：18
//解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
//可以证明不存在总和小于 18 的 k-avoiding 数组。
// 
//
// 示例 2： 
//
// 
//输入：n = 2, k = 6
//输出：3
//解释：可以构造数组 [1,2] ，其元素总和为 3 。
//可以证明不存在总和小于 3 的 k-avoiding 数组。 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n, k <= 50 
// 
//
// Related Topics 贪心 数学 👍 35 👎 0


package LeetCode.editor.cn;


import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-03-26 12:08:50
 * @description 2829.k-avoiding 数组的最小总和
 
 */
 
public class DetermineTheMinimumSumOfAKAvoidingArray {
    public static void main(String[] args) {
    //测试代码
    DetermineTheMinimumSumOfAKAvoidingArray fun = new DetermineTheMinimumSumOfAKAvoidingArray();
    Solution solution= fun.new Solution();
    solution.minimumSum(4,5);
//    1 2 6 5
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*先求和1~n
        * 然后从1到k遍历，如果存在元素对(a,k-a)
        * 原和减去较大的那一个，然后从n+1开始补
        * 如果补入的数c,存在(k-c),则遍历到不存在k-c为止
        *
        * */
    public int minimumSum1(int n, int k) {
        Set<Integer> set=new HashSet<>();
        for (int i = 1; i <=n; i++) {
            set.add(i);
        }
        int res=(1+n)*n/2;
        int ind=n+1;
        for (int i = 1; i < k; i++) {
            if(!set.contains(i)) continue;
            int a=k-i;
            if(a==i) continue;
            if (set.contains(a)){
                while (set.contains(k-ind)){
                    ind++;
                }
                set.remove(a);
                res+=(ind-a);
                set.add(ind++);
            }
        }
        return res;
    }

    //如果某个数在数组中，则k-a，一定不能在
    //从1开始放入，直到[k/2]，如果这个数组已经达到n个了，就从k开始继续加入数组，加入k-[k/2]个数字加入，
    //最终的结果是一个或者两个等差数列
    public int minimumSum(int n, int k) {
        if (n <= k / 2) {
            return arithmeticSeriesSum(1, 1, n);
        } else {
            return arithmeticSeriesSum(1, 1, k / 2) + arithmeticSeriesSum(k, 1, n - k / 2);
        }
    }

    private int arithmeticSeriesSum(int a1, int d, int n) {
        return (a1 + a1 + (n - 1) * d) * n / 2;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
